package afi;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import core.BinarySearch;

public class ArrayIntersect {

	/**
	 * Problem 1.7 in AFI:
	 * Finds the intersection of two sorted integer arrays without duplicates
	 * @param a first integer array
	 * @param b second integer array
	 * @return sorted intersection of elements in the array without duplicates
	 */
	public static int[] intersectSortedArrays(int[] a, int[] b) {
		// worst case size for the intersection array
		int[] c = new int[Math.min(a.length, b.length)];
		int ai = 0, bi = 0, ci = 0;

		while (ai < a.length && bi < b.length) {
			if (a[ai] == b[bi]) {
				// check if element already exists
				if (ci == 0 || a[ai] != c[ci - 1]) {
					c[ci++] = a[ai];
				}
				ai++;
				bi++;
			} else if (a[ai] > b[bi]) {
				bi++;
			} else if (a[ai] < b[bi]) {
				ai++;
			}
		}

		return Arrays.copyOfRange(c, 0, ci);
	}
	
	
	/**
	 * Binary search implementation of array intersection
	 * @param a first integer array
	 * @param b second integer array
	 * @return sorted intersection of elements in the array without duplicates
	 */
	public static int[] intersectSortedArrays2(int[] a, int[] b) {
		// worst case size for the intersection array
		int[] c = new int[Math.min(a.length, b.length)];
		int ci = 0;

		for(int element : a){
			if(BinarySearch.search(b, element) >= 0){
				if(ci == 0 || c[ci-1] != element){
					c[ci++] = element;
				}
			}
		}

		return Arrays.copyOfRange(c, 0, ci);
	}
	
	
	/**
	 * Hashing implementation of array intersection
	 * @param a first integer array
	 * @param b second integer array
	 * @return sorted intersection of elements in the array without duplicates
	 */
	public static int[] intersectSortedArrays3(int[] a, int[] b) {
		// worst case size for the intersection array
		int[] c = new int[Math.min(a.length, b.length)];
		int ci = 0;
		
		Set<Integer> set = new HashSet<Integer>();

		for(int element : a){
			set.add(element);
		}
		
		for(int element : b){
			if(set.contains(element)){
				c[ci++] = element;
			}
		}

		return Arrays.copyOfRange(c, 0, ci);
	}
}
